home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_02 / otto / bm.c < prev    next >
C/C++ Source or Header  |  1993-12-01  |  6KB  |  242 lines
  1. /************************************************
  2.  *    Fast String Search
  3.  *
  4.  * Using a tuned Boyer and Moore algorithm.
  5.  *
  6.  * This source code is written by Erick Otto. 
  7.  * Algorithms from Daniel Sunday and Andrew Hume 
  8.  * are used in this code.
  9.  *
  10.  * 1993 by Erick Otto.
  11.  * 
  12.  */
  13.  
  14. #include    <stdio.h>
  15. #include    <fcntl.h>
  16. #include    "freq.h"
  17.  
  18. /* Size of text buffer, BUFSIZ */
  19. /* is optimum from stdio.h     */
  20. #define TBUF (8*BUFSIZ)    
  21.  
  22. #define MAXPAT 256
  23.  
  24. /* We use the following variables for the search */
  25. /*                                               */
  26. /* pat    : The pattern                          */
  27. /* dist   : A table which contains the offsets   */
  28. /*          for every char in the pattern from   */
  29. /*          the end of the pattern               */
  30. /* lfc    : The least frequent char in the patt  */
  31. /* lfcoff : The offset of lfc from end of patt   */
  32. /* shift  : The leftward re-occurance of the     */
  33. /*          last charater in positions from the  */
  34. /*          end of the patt                      */
  35.  
  36. int patlen;
  37. unsigned char pat[MAXPAT];
  38. unsigned char dist[MAXPAT];
  39. int lfc, lfcoff;
  40. int shift;
  41.  
  42. main(argc, argv)
  43. int argc;
  44. char **argv;
  45. {
  46.     char buf[TBUF+MAXPAT];
  47.     char match[MAXPAT];
  48.     register int fd, nread;
  49.     register char *beg, *lastnl, *end;
  50.     char filename[80];
  51.  
  52.     /* must be at least one arguments */
  53.     if (argc < 2 ) {
  54.         fprintf(stderr,"\n\tMatch string expected\n");
  55.         exit();
  56.     }
  57.     if (argc < 3 ) {
  58.         fprintf(stderr,"\n\tFilename expected\n");
  59.         exit();
  60.     }
  61.  
  62.     strcpy(match, argv[1]);
  63.     strcpy(filename, argv[2]);
  64.     build(match, strlen(match));
  65.  
  66.     if ((fd = open(filename,O_RDONLY)) == -1) {
  67.         fprintf(stderr,
  68.        "Can't open file %s\n", filename);
  69.         perror(filename);
  70.         exit(1);
  71.     }
  72.     
  73.     *buf = '\n'; /* sentinel for printing purposes */
  74.     beg = buf+1;
  75.  
  76.     while((nread=read(fd,beg,(&buf[TBUF]-beg)))>0){
  77.         end = beg+nread;
  78.         lastnl = end;
  79.         while(*--lastnl != '\n') ;
  80.  
  81.         /* lastnl points to the newline */
  82.         matchpat(buf+1, lastnl-buf);
  83.  
  84.         memcpy(buf+1, lastnl, end-lastnl-1);
  85.         beg = buf + 1 + (end-lastnl);
  86.     }
  87.     close(fd);
  88. }
  89.  
  90. build(match, m)
  91. unsigned char *match;
  92. register m;
  93. {
  94.     register unsigned char *patend, *patptr;
  95.     register unsigned char *d;
  96.     register int i;
  97.     register unsigned char *pos;
  98.     unsigned char *lastchar;
  99.     int lfcidx;
  100.  
  101.     if(m > MAXPAT) {
  102.         printf("Length of the pattern too long!\n");
  103.         exit(1);
  104.     }
  105.  
  106.     /* initialize the pattern variables */
  107.     patlen = m;
  108.     memcpy(pat, match, patlen);
  109.  
  110.     /* build the dist table */
  111.     d = dist;
  112.  
  113.     /* initialize all elements to the pattern length */
  114.     for(i = 0; i < MAXPAT; i++)
  115.         d[i] = patlen;
  116.  
  117.     /* set all characters in the pattern    */
  118.     /* to their relative distances from the */
  119.     /* end of the pattern                   */
  120.  
  121.     patptr = pat; 
  122.     patend = patptr+patlen-1;
  123.  
  124.     while(patptr < patend) {
  125.         d[*patptr] = patend-patptr;
  126.         patptr++;
  127.     }
  128.     d[*patptr] = 0;
  129.  
  130.     /* find the least frequent character */
  131.     /* that occurs in the pattern        */
  132.  
  133.     lfcidx = 0;
  134.     for(i = 1; i < patlen; i++){
  135.         if(freq[pat[i]] < freq[pat[lfcidx]])
  136.             lfcidx = i;
  137.     }
  138.  
  139.     /* set the lf char and offset for  */
  140.     /* later use                       */
  141.     lfc = pat[lfcidx];
  142.     lfcoff = lfcidx - (patlen-1);
  143.  
  144.     /* Look backward and see if we can */
  145.     /* find an other occurance of the  */
  146.     /* same character as the last one  */
  147.     lastchar = patptr;
  148.     for(pos = lastchar-1; pos >= pat; pos--)
  149.         if (*pos == *lastchar) break;
  150.  
  151.     /* record the occurance for later use */
  152.     shift = lastchar - pos;    
  153. }
  154.  
  155. matchpat(text, n)
  156. unsigned char *text;
  157. int n;
  158. {
  159.     register unsigned char *e, *s;
  160.     register unsigned char *dp;
  161.     register int k;
  162.     register int lfco, lfcc;
  163.     register unsigned char *p, *q;
  164.     register unsigned char *ep;
  165.     register char *sp;
  166.     register char *nl;
  167.     register int t1;
  168.     char save[MAXPAT];
  169.  
  170.     dp = dist;
  171.     t1 = patlen-1;
  172.     sp = save;
  173.     s = text+t1;
  174.     e = text+n;
  175.     memcpy(sp, e, patlen);
  176.     memset(e, pat[t1], patlen);
  177.     lfco = lfcoff;
  178.     lfcc = lfc;
  179.     ep = pat + t1;
  180.  
  181.  
  182.     while(s < e){
  183.  
  184.         /* fast forward through the text  */
  185.         /* untill we find the last char   */
  186.         /* of the pattern (unrolled loop) */
  187.  
  188.         k = dp[*s];
  189.         while(k){
  190.             k = dp[*(s += k)];
  191.             k = dp[*(s += k)];
  192.             k = dp[*(s += k)];
  193.         }
  194.  
  195.         /* If we hit the sentinel at */
  196.         /* the end of the buffer we  */
  197.         /* are done with the buffer  */
  198.         if(s >= e)
  199.             break;
  200.  
  201.         /* Neat little trick, actually  */
  202.         /* makes things faster. Do a    */
  203.         /* pre check on the lfc, before */
  204.         /* starting the full comparison */
  205.         if(s[lfco] != lfcc)
  206.             goto mismatch;
  207.  
  208.         /* normal forward string matching */
  209.         for(p = pat, q = s-t1; p < ep; ){
  210.             if(*q++ != *p++)
  211.                 goto mismatch;
  212.         }
  213.  
  214.         /** A match has been found **/
  215.         /*  at position q - patlen  */
  216.  
  217.         nl=q;    
  218.  
  219.         /* look back for the closest newline */
  220.     
  221.         while(*--nl != '\n')
  222.             ;
  223.         while(*++nl != '\n') putchar(*nl);
  224.         putchar('\n');
  225.  
  226.         /* we are now at q which is somewhere in 
  227.      * the text we reported a match by 
  228.      * printing the line, so any possible 
  229.      * other matches will NOT have to be 
  230.      * searched for in this line so forward 
  231.      * to the end of line
  232.          */
  233.          q=nl;
  234.  
  235.     mismatch:
  236.     /* use the shift that we calculated */
  237.         s += shift;
  238.     }
  239.     memcpy(e, sp, patlen);
  240.     return(0);
  241. }
  242.